/**
 * 621. 任务调度器
 * https://leetcode-cn.com/problems/task-scheduler/
 */

/**
 * @param {string[]} tasks
 * @param {number} n
 * @return {number}
 */
function leastInterval(tasks, n) {
  const map = new Map();
  const scheduler = [];
  for (let i = 0; i < tasks.length; i += 1) {
    const task = tasks[i];
    if (map.has(task)) {
      map.get(task).count += 1;
    } else {
      const message = {
        name: task,
        count: 1,
        lastExecuteTime: -Infinity,
      };
      map.set(task, message);
      scheduler.push(message);
    }
  }
  map.clear();
  scheduler.sort((a, b) => b.count - a.count);
  let leftCount = tasks.length;
  let time = 0;
  // let log = '';
  while (leftCount) {
    let target = null;
    let index = -1;
    for (let i = 0; i < scheduler.length; i += 1) {
      const message = scheduler[i];
      if (message.count && time - message.lastExecuteTime > n) {
        target = message;
        index = i;
        break;
      }
    }
    if (target) {
      target.count -= 1;
      target.lastExecuteTime = time;
      leftCount -= 1;
      scheduler.splice(index, 1);
      let nextIndex = index;
      let next = scheduler[nextIndex];
      while (
        nextIndex < scheduler.length
        && (
          target.count < next.count
          ||
          (target.count === next.count && target.lastExecuteTime > next.lastExecuteTime)
        )
      ) {
        nextIndex += 1;
        next = scheduler[nextIndex];
      }
      scheduler.splice(nextIndex, 0, target);
      // log += target.name;
    } else {
      // log += '-';
    }
    time += 1;
  }
  // console.log(log);
  return time;
}

console.log(leastInterval(['A', 'A', 'A', 'B', 'B', 'B'], 2) === 8);
console.log(leastInterval(['A', 'A', 'A', 'B', 'B', 'B'], 0) === 6);
console.log(leastInterval(['A', 'A', 'A', 'A', 'A', 'A', 'B', 'C', 'D', 'E', 'F', 'G'], 2) === 16);
console.log(leastInterval(['A'], 2) === 1);
console.log(leastInterval(['A', 'A', 'A', 'B', 'B', 'B', 'C', 'C', 'C', 'D', 'D', 'E'], 2) === 12);
console.log(leastInterval(['A', 'A', 'B', 'B', 'C', 'C', 'D', 'D', 'E', 'E', 'F', 'F', 'G', 'G', 'H', 'H', 'I', 'I', 'J', 'J', 'K', 'K', 'L', 'L', 'M', 'M', 'N', 'N', 'O', 'O', 'P', 'P', 'Q', 'Q', 'R', 'R', 'S', 'S', 'T', 'T', 'U', 'U', 'V', 'V', 'W', 'W', 'X', 'X', 'Y', 'Y', 'Z', 'Z'], 2) === 52);
